//在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 
//
// 
//
// 示例 1: 
//
// 输入: [7,5,6,4]
//输出: 5 
//
// 
//
// 限制： 
//
// 0 <= 数组长度 <= 50000 
// Related Topics 树状数组 线段树 数组 二分查找 分治 有序集合 归并排序 👍 609 👎 0

package com.cute.leetcode.editor.cn;

import java.util.Arrays;

public class ShuZuZhongDeNiXuDuiLcof {
    public static void main(String[] args) {
        int[] nums = {1,3,2,3,1};
        new ShuZuZhongDeNiXuDuiLcof().new Solution().reversePairs(nums);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 维护了一个单调数组
         * 这样做还真实现了
         * 就是时间上是最快时间的十倍多
         */
        public int reversePairs1(int[] nums) {
            if (nums.length == 0) return 0;
            int[] sort = new int[nums.length];
            sort[0] = nums[0];
            int res = 0;
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] < sort[i - 1]) {
                    res += i;
                    sort[i] = nums[i];
                }else res += insert(sort, nums[i], i);
            }
            return res;
        }
        /**
         * 维护一个单调减的数组，实现搜索位置以及插入
         * 主要是移动的时候费时间
         * 返回值是前边元素的个数
         */
        private int insert(int[] sort, int val, int index) {
            int left = 0;
            int right = index - 1;
            int mid;
            while (left < right){
                mid = left + (right - left) / 2;
                if (sort[mid] > val) left = mid + 1;
                else right = mid;
            }
            if (index - left >= 0) System.arraycopy(sort, left, sort, left + 1, index - left);
            sort[left] = val;
            return left;
        }

        /**
         * 看了以下剑指Offer的题解，可以使用归并排序的思路进行统计
         * 先分再治，分的话好说，主要是需要再合并时统计逆序对的个数
         * 以7 5 6 4为例
         * 分到最后为
         * 7   5   6   4
         * 1.合并时7与5进行比较，目标是找到左边>右边的值并统计个数
         *      下标分别从两部分的初始位置开始，即ij分别指向7 5，此时由于7 > 5，则需要进行统计，计数为1，并将5添加回数组，使数组保持递增，所以合并为5 7
         *      6 4 合并时同理，计数为1，合并为4 6
         * 2. 合并5 7      4 6
         *      1.此时ij分别指向5 4，mid为中间下标为1，此时5>4进行计数2：因为mid-i+1 = 2（5即之后所有数都统计），向数组添加4，j指向6
         *      2.由于i指向5<6，所以向数组添加5，此时数组为4 5，i指向7
         *      3.当i指向7时>6，再次计数为1，添加6
         *      4.此时右边已空，将左边所有元素进行添加即可
         */
        public int reversePairs(int[] nums) {
            if(nums.length == 0) return 0;
            int[] copy = new int[nums.length];
            return merge(nums, copy, 0, nums.length - 1);
        }
        private int merge(int[] data, int[] copy, int start, int end) {
            if (start >= end) return 0;
            int mid = (end + start) / 2;
            int count = merge(data, copy, start, mid) + merge(data, copy, mid + 1, end);
            int i = start;// 左半部分起始
            int j = mid + 1;// 右半部分起始
            for (int k = start; k <= end; k++) copy[k] = data[k];// 保存归并前的顺序
            for (int k = start; k <= end; k++) {
                if (i == mid + 1) data[k] = copy[j++];// 这里说明左半部分已经归并完了，只需要归并右半部分
                // 这里说明右半部分归并完了，或者左边出现了较小的值，需要添加左边的元素
                else if (j == end + 1 || copy[i] <= copy[j]) data[k] = copy[i++];
                else {// 这里就是左边大于右边的时候，进行计数并搬移右边
                    data[k] = copy[j++];
                    count += mid - i + 1;// 统计左边剩下的所有元素个数
                }
            }
            return count;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}